HW#3 --- last modified February 06 2019 04:07:27..

Solution set.

Due date: Apr 5

Files to be submitted:
  Hw3.zip

Purpose: Gain some intuition about the relative hardness of different computational problems

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO3 -- Show the completeness of a complete problem for each of these classes.

CLO5 -- Know conditions under which various of these hierarchies might collapse.

CLO8 -- Exhibit a relativized separation (oracle result) of complexity classes for standard classes such as P and NP.

Specification:

For this homework I would like you to write up solutions to the problems below. If possible, write up the homework in LaTeX. If you use Word, format any math by using the math equation editor. Once you have prepared your solution output it as a PDF and submit it as Hw3.pdf. Be aware that the maximum-sized document that the upload system supports is 10 MB.

1. We define a p-time, CNF proof system to be a TM `M(x,y)` that operates in `p(|(x,y)|)` for some polynomial `p` such that: (1) when `y` is an encoding of a valid CNF formula, a tautology, then there is some `x` on which `M` will output 1 on input the encoding of the pair `(x,y)`, (2) when `y` is not a tautology, then `M` will output 0 for any `x`. Call such a proof system super if whenever `y` is a tautology, there exists an `x` of size at most `q(|y|)`, where `q` is a polynomial, that makes `M` output 1. Prove that if a super, p-time, CNF proof system exists then `NP = co-NP`.
2. Modify our 5.19 bound threshold proof under which 3-SAT instances are almost surely unsatisfiable to a bound under which 5-SAT instances are almost surely unsatisfiable.
3. Prove the general case of the deterministic time hierarchy theorem presented in class.
4. Imagine that we expand the definition of CNF formula to allow clauses to include literals of the form `A(x_1, ..., x_n)` and `not A(x_1, ..., x_n)` for some language `A`. Literal `A` is true if under a variable assignment the string represented by `x_1 ...x_n` is in the language `A`. Let `TAUT^A` denote the problem of determining if a CNF formula expanded with `A` clauses is valid. Prove this problem is `coNP^A`-complete. Show there exists an `A` such that `TAUT^A` is not in `P^A`.
5. In our proof of Ladner's theorem we asserted that "the existence of such a reduction to smaller SAT instances yields a simple polynomial time algorithm for SAT". Show why this is true.

Point Breakdown